﻿归并分治板子题3：牛客 计算数组的小和
测试链接：https://www.nowcoder.com/practice/edfe05a1d45c4ea89101d936cac32469

————————————————————————————————————————————————————————————————————————————————————————————————————————————
思路分析：


1.核心算法框架：基于归并排序
递归分治：将原数组不断分成左右两部分，直到子数组只包含一个元素。
合并排序：每次将左右两个有序子数组合并为一个有序数组。
在合并的同时，计算跨左右两部分的小和。


2. 核心计算步骤
---(1) 递归拆分数组
使用 sortAndCount(l, r) 对[l, r] 范围内的数组递归排序，并返回该范围内的总小和。
左半部分：sortAndCount(l, mid)，计算左半部分的总小和。
右半部分：sortAndCount(mid + 1, r)，计算右半部分的总小和。
跨左右部分：调用 merge(l, r, mid)，计算右半部分对左半部分产生的小和。

---(2) 合并和计算小和
使用 merge(l, r, mid) 函数：
遍历右半部分的元素[mid + 1, r]，对于每个右侧元素 nums[k]，找到左半部分[l, mid] 中所有小于等于 nums[k] 的元素并将其值累加到小和中。

利用左、右部分的有序性：
遍历右半部分时，左半部分的指针 j 只会向右移动，不会回退，避免重复计算，时间复杂度为𝑂(𝑛)

合并两个有序数组：
将左右两部分有序子数组合并成一个有序数组，同时使用辅助数组 help 暂存排序结果。


3. 辅助数组的作用
help 数组 用于在合并排序过程中暂时存储排序后的结果，避免直接修改原数组 num。
合并完成后，将 help 数组中的有序结果复制回原数组 num。


4. 时间复杂度分析
归并排序的复杂度：
每次递归将数组对半拆分，递归深度为O(logn)。
每次合并的复杂度为O(n)。
因此总复杂度为O(nlogn)。

计算小和的复杂度：
每次合并时利用指针不回退的特性，统计小和的复杂度为O(n)。

总复杂度与归并排序一致，仍为O(nlogn)。
————————————————————————————————————————————————————————————————————————————————————————————————————————————

AC代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

// 这里声明了两个全局数组，一个用于存储原始数组，一个用于存储合并排序的辅助数组
vector<int> num(100010);    // 原始数组，存储输入的数
vector<int> help(100010);   // 辅助数组，存储排序过程中合并后的数据

//marge 函数：计算 跨越左右产生的 答案（小和的累加和）
//目的：统计[mid+1,r]区间中每个元素 在 [l,mid]中产生的小和的 累加和
//由于利用了 各子区间的有序性， 所以在计算完毕后 需要将两个子区间 合并成一个有序区间
ll merge(int l, int r, int mid, vector<int>& num, vector<int>& help) 
{
    ll ans = 0;  // 统计 [mid+1,r]中每个元素 在 [l,mid]中产生的小和的 累加和
    ll sum = 0;  // 统计 [mid+1,r]中每个元素 在 [l,mid]中产生的小和
    //***由于 左右两部分有序：故指向左半部分的指针是不回退的***

    int j = l;   // j指向左半部分的起始位置

    // 遍历右半部分，计算小和（左跨右部分的小和）
    //k控制右半部分；j控制左半部分
    for (int k = mid + 1; k <= r; k++)
    {
        //每个 左跨右产生的小和 sum 最多加到 mid位置
        while (j <= mid && num[j] <= num[k]) 
        {
            sum += num[j];  // 将左半部分元素的值加到 sum 中
            j++;  // 移动左半部分的指针
        }
        ans += sum;  // 计算小和，把当前的 sum 加到 ans 中
    }





    // 正常marge:合并两个已排序的子数组
    int a = l, b = mid + 1, i = l;
    // 合并左右两部分，确保合并后的数组仍然是有序的
    while (a <= mid && b <= r) 
    {
        if (num[a] <= num[b]) 
        {
            help[i] = num[a];  // 如果左半部分元素小于等于右半部分元素，将其放到辅助数组中
            a++;
        }
        else 
        {
            help[i] = num[b];  // 如果右半部分元素小于左半部分元素，将其放到辅助数组中
            b++;
        }
        i++;  // 移动辅助数组的指针
    }

    // 将左半部分剩余的元素复制到辅助数组中
    while (a <= mid) 
    {
        help[i] = num[a];
        a++;
        i++;
    }

    // 将右半部分剩余的元素复制到辅助数组中
    while (b <= r) 
    {
        help[i] = num[b];
        b++;
        i++;
    }

    // 将辅助数组中的排序结果复制回原数组
    for (int j = l; j <= r; j++) 
    {
        num[j] = help[j];  // 这样就完成了左右两部分的合并
    }

    return ans;  // 返回当前合并过程中的小和
}

// 归并排序的主函数，递归地排序并计算小和
ll sortAndCount(int l, int r, vector<int>& num, vector<int>& help) 
{
    if (l == r)
    {
        return 0;  // 基准条件，只有一个元素时没有小和
    }

    int mid = (l + r) / 2;  // 计算中间位置
    //***递归排序并计算左半部分产生的小和、右半部分产生的小和、以及左跨右时(右半部分产生的小和)***
    return sortAndCount(l, mid, num, help) + sortAndCount(mid + 1, r, num, help) + merge(l, r, mid, num, help);
}

int main() 
{
    int n;
    cin >> n;  // 输入数组的大小

    vector<int> num(n);  // 初始化原始数组
    vector<int> help(n);  // 初始化辅助数组

    // 输入数组元素
    for (int i = 0; i < n; i++) 
    {
        cin >> num[i];
    }

    // 调用sortAndCount函数计算小和
    ll result = sortAndCount(0, n - 1, num, help);

    // 输出最终结果
    cout << result << endl;

    return 0;
}